import numpy as np
import random


def dp1_with_resource(value_res_dict: dict, resource_bound):
    """
    使用动态规划（标签设置算法）求解带资源约束的最大价值问题，行动维度为1
    :param value_res_dict:
    :param resource_bound:
    :return:
    """
    states = []
    new_states = []
    is_first = True
    for i in value_res_dict.keys():
        if is_first:
            is_first = False
            for j, (value, res) in value_res_dict[i].items():
                if res > resource_bound:
                    continue
                block = Block(i, j, None, value, res)
                new_states.append(block)
        else:
            for state in states:
                for j, (value, res) in value_res_dict[i].items():
                    if res + state.res > resource_bound:
                        continue
                    block = Block(i, j, state, value + state.val, res + state.res)
                    new_states.append(block)
        new_states = sorted(new_states, reverse=True)
        if len(new_states) == 0:
            return None
        states = []
        res_bd = new_states[0].res + 1
        for state in new_states:
            if state.res < res_bd:
                states.append(state)
                res_bd = state.res
        new_states = []
    return states[0]


class Block:
    """
    带资源条件的比较器
    """

    def __init__(self, num, act, from_act, val, res):
        """
        :param val:价值，越大越好。主要目标
        :param res: 资源消耗，越小越好。次要目标
        """
        self.val = val
        self.res = res
        self.num = num
        self.act = act
        self.from_act = from_act

    def domain(self, other):
        if self.val >= other.val and self.res <= other.res:
            return 1
        elif self.val < other.val and self.res > other.res:
            return -1
        return 0

    def __lt__(self, other):
        if self.val < other.val or (self.val == other.val and self.res > other.res):
            return 1
        return 0

    def __eq__(self, other):
        return self.val == other.val and self.res == other.res

    def __gt__(self, other):
        if self.val > other.val or (self.val == other.val and self.res < other.res):
            return 1
        return 0

    def __le__(self, other):
        return self.__lt__(other) or self.__eq__(other)

    def __ge__(self, other):
        return self.__gt__(other) or self.__eq__(other)


class Parameters:
    def __init__(self, total_period, t1_vf_cost, t2_vf_cost, t1_vv_cost, t2_vv_cost,
                 volume: np.ndarray, weight: np.ndarray, process_cost: np.ndarray, prices: np.ndarray):
        # 以下是从excel表里读取的数据
        self.total_period = total_period  # 规划周期
        self.t1_vf_cost = t1_vf_cost  # t1的车辆使用成本
        self.t2_vf_cost = t2_vf_cost  # t2的车辆使用成本
        self.t1_vv_cost = t1_vv_cost  # t1的车辆运输成本（元/吨公里）
        self.t2_vv_cost = t2_vv_cost  # t2的车辆运输成本（元/吨公里）
        self.volume = volume  # 各产品体积
        self.weight = weight  # 各产品重量
        self.process_cost = process_cost  # 各产品的处理成本
        self.prices = prices  # 各产品的售价

        # 以下是算法要用的数据
        self.t1_list = []
        self.t2_list = []
        self.t3_list = []
        self.dist12 = np.zeros((0, 0))  # t1和t2的距离矩阵
        self.dist23 = np.zeros((0, 0))  # t2和t3的距离矩阵
        self.ppl = []  # 种群
        self.ppl_num = 0  # 种群数量
        self.best = None  # 最优解（只有序列sequence，没有目标值）
        self.best_revenue = -1e+50  # 最优解的收益

        self.period1_list = [2, 3, 5]  # t1的备选周期集合
        self.period2_list = [2, 3, 5]  # t2的备选周期集合

        self.cross_rate = 0.5
        self.factor = 1.5
        self.muta_rate = 0.2

    def set_population_num(self, ppl_num):
        self.ppl_num = ppl_num


class T1:

    def __init__(self, num, lat, lng, s_1day: np.ndarray, recall_cost: np.ndarray, hold_cost: np.ndarray):
        self.num = num  # 编号
        self.lat = lat  # 维度
        self.lng = lng  # 经度
        self.s_1day = s_1day  # 各产品每天的供应数量
        self.recall_cost = recall_cost  # 各产品的回收成本
        self.hold_cost = hold_cost  # 各产品的持有成本（元/台天）


class T2:

    def __init__(self, num, lat, lng, cap, open_cost, hold_cost: np.ndarray):
        self.num = num  # 编号
        self.lat = lat  # 维度
        self.lng = lng  # 经度
        self.cap = cap  # 容量
        self.open_cost = open_cost  # 开放成本
        self.hold_cost = hold_cost  # 各产品的持有成本
        self.best_t3 = None  # 最优的t3分配对象

    def set_best_t3(self, dist23, t3_list):
        self.best_t3 = t3_list[np.argmin(dist23[self.num])]


class T3:

    def __init__(self, num, lat, lng):
        self.num = num  # 编号
        self.lat = lat  # 维度
        self.lng = lng  # 经度


class Chromosome:

    def __init__(self, strategy, t1_num, t2_num):
        """
        构造方法
        :param strategy:选择产生sequence的方法，0表示随机策略
        """
        self.sequence = np.zeros(t1_num)  # 染色体序列（数字标识，数字是t1的索引或者编号）
        self.opened_t2 = set()  # 开放的t2的索引或编号
        self.term_1 = dict()  # 第一阶段各t1的运输周期
        self.t2_arrival_q = dict()  # 各开放的t2每天到货量
        self.term_2 = dict()  # 第二阶段各开放的t2的运输周期
        self.total_revenue = 0  # 总收入
        self.infeasible = False
        if strategy == 0:
            self.get_sequence_random(t1_num, t2_num)

    def clear(self):
        """
        sequence不需要clear，调用set_sequence即可，或者直接在sequence上更新
        :return:
        """
        self.opened_t2.clear()
        self.term_1.clear()
        self.term_2.clear()
        self.t2_arrival_q.clear()
        self.total_revenue = 0
        self.infeasible = False

    def set_sequence(self, sequence):
        self.sequence = sequence

    def get_sequence_random(self, t1_num, t2_num):
        self.sequence = np.random.randint(0, t2_num, t1_num)

    def get_opened_t2(self):
        self.opened_t2 = set(self.sequence)

    def get_t1_vf_cost_per(self, t, pr: Parameters):
        times = pr.total_period / t
        return times * pr.t1_vf_cost

    def get_t1_vv_cost_per(self, i, j, pr: Parameters):
        t1 = pr.t1_list[i]
        t2 = pr.t2_list[j]
        assert isinstance(t1, T1)
        dij = pr.dist12[t1.num, t2.num]
        cost = pr.total_period * dij * pr.t1_vv_cost * np.sum(pr.weight * t1.s_1day)
        return cost

    def get_t1_hold_cost_per(self, i, t, pr: Parameters):
        t1 = pr.t1_list[i]
        assert isinstance(t1, T1)
        cost = t * 0.5 * np.sum(t1.s_1day * t1.hold_cost) * pr.total_period
        return cost

    def get_t1_arrival_volume_per(self, i, t, pr: Parameters):
        t1 = pr.t1_list[i]
        assert isinstance(t1, T1)
        quantity = np.sum(t1.s_1day * pr.volume) * t
        return quantity

    def parse_state(self, state: Block):
        while state is not None:
            self.term_1[state.num] = state.act
            state = state.from_act

    def get_best_period_1_per(self, j, pr: Parameters):
        t2 = pr.t2_list[j]
        assert isinstance(t2, T2)
        t2_covers = []
        for i in range(len(self.sequence)):
            if self.sequence[i] == t2.num:
                t2_covers.append(i)
        val_res_dict = dict()
        for i in t2_covers:
            val_res_dict[i] = dict()
            for term in pr.period1_list:  # 表周期
                t1_vf_cost = self.get_t1_vf_cost_per(term, pr)
                t1_vv_cost = self.get_t1_vv_cost_per(i, j, pr)
                t1_hold_cost = self.get_t1_hold_cost_per(i, term, pr)
                t1_need_cost = t1_vf_cost + t1_vv_cost + t1_hold_cost
                t1_quantity = self.get_t1_arrival_volume_per(i, term, pr)
                val_res_dict[i][term] = (-t1_need_cost, t1_quantity)
        state = dp1_with_resource(val_res_dict, t2.cap)
        if state is None:
            self.infeasible = True
        else:
            self.parse_state(state)

    def get_t2_arrival_q(self, pr: Parameters):
        for i, t in self.term_1.items():
            t1 = pr.t1_list[i]
            assert isinstance(t1, T1)
            j = self.sequence[i]
            if j not in self.t2_arrival_q.keys():
                self.t2_arrival_q[j] = np.zeros((1 + pr.total_period, pr.volume.size))  # (周期+1) * 产品
            for stage in range(1, pr.total_period // t + 1):
                k = stage * t
                self.t2_arrival_q[j][k] += (t * t1.s_1day)

    def get_t2_stock_per(self, j, t, pr: Parameters):
        stock = np.zeros((pr.total_period + 1, pr.volume.size))
        for k in range(1, len(stock)):
            if k % t != 0:
                # try:
                stock[k] = self.t2_arrival_q[j][k] + stock[k - 1]
                """except KeyError:
                    print("sequence: ", self.sequence)
                    print("open: ", self.opened_t2)
                    print("stock:", stock)
                    print("k = ", k)
                    print("j = ", j)
                    print("arrival_q = ", self.t2_arrival_q)
                    exit(-1)"""
        return stock

    def get_t2_hold_cost_per(self, j, stock: np.ndarray, pr: Parameters):
        t2 = pr.t2_list[j]
        assert isinstance(t2, T2)
        return np.sum(stock * t2.hold_cost)

    def get_t2_vf_cost_per(self, t, pr: Parameters):
        times = pr.total_period / t
        return times * pr.t2_vf_cost

    def get_t2_vv_cost_per(self, j, pr: Parameters):
        t2 = pr.t2_list[j]
        assert isinstance(t2, T2)
        t3 = t2.best_t3
        dist = pr.dist23[t2.num, t3.num]
        quantity = np.zeros(pr.weight.size)
        for i in range(len(self.sequence)):
            if self.sequence[i] == j:
                t1 = pr.t1_list[i]
                assert isinstance(t1, T1)
                quantity += (t1.s_1day * pr.total_period)
        return np.sum(quantity * pr.weight) * dist * pr.t2_vv_cost

    def get_best_period_2_per(self, s, pr: Parameters):
        t3_covers = []
        for j in self.opened_t2:
            t2 = pr.t2_list[j]
            assert isinstance(t2, T2)
            if t2.best_t3.num == s:
                t3_covers.append(j)
        for j in t3_covers:
            best_term = -1
            best_cost = 1e+50
            for t in pr.period2_list:
                t2_vf_cost = self.get_t2_vf_cost_per(t, pr)
                stock = self.get_t2_stock_per(j, t, pr)
                t2_hold_cost = self.get_t2_hold_cost_per(j, stock, pr)
                cost = t2_vf_cost + t2_hold_cost
                if cost < best_cost:
                    best_cost = cost
                    best_term = t
            self.term_2[j] = best_term

    def get_term(self, pr: Parameters):
        self.get_opened_t2()
        used_t3 = set()
        for j in self.opened_t2:
            self.get_best_period_1_per(j, pr)
            if self.infeasible:
                break
            used_t3.add(pr.t2_list[j].best_t3.num)
        if not self.infeasible:
            self.get_t2_arrival_q(pr)
            """if len(self.term_1) != len(pr.t1_list):
                print("bug!")
            if set(self.t2_arrival_q.keys()) != self.opened_t2:
                print('bug')"""
            for s in used_t3:
                self.get_best_period_2_per(s, pr)

    def get_recall_cost_per(self, i, pr: Parameters):
        t1 = pr.t1_list[i]
        assert isinstance(t1, T1)
        return np.sum(t1.recall_cost * t1.s_1day) * pr.total_period

    def get_process_cost_per(self, j, pr: Parameters):
        quantity = np.zeros(pr.weight.size)
        for i in range(len(self.sequence)):
            if self.sequence[i] == j:
                t1 = pr.t1_list[i]
                assert isinstance(t1, T1)
                quantity += (t1.s_1day * pr.total_period)
        return np.sum(quantity * pr.process_cost)

    def get_open_cost_per(self, j, pr: Parameters):
        return pr.t2_list[j].open_cost

    def get_earning(self, pr: Parameters):
        quantity = np.zeros(pr.weight.size)
        for t1 in pr.t1_list:
            quantity += t1.s_1day * pr.total_period
        return np.sum(quantity * pr.prices)

    def get_total_revenue(self, pr: Parameters):
        if self.infeasible:
            self.total_revenue = -1e+50
            return
        t1_vf_cost = 0
        t1_vv_cost = 0
        t1_hold_cost = 0
        recall_cost = 0
        t2_vf_cost = 0
        t2_vv_cost = 0
        t2_hold_cost = 0
        t2_process_cost = 0
        open_cost = 0
        earning = self.get_earning(pr)
        for i, term in self.term_1.items():
            j = self.sequence[i]
            t1_vf_cost += self.get_t1_vf_cost_per(term, pr)
            t1_vv_cost += self.get_t1_vv_cost_per(i, j, pr)
            t1_hold_cost += self.get_t1_hold_cost_per(i, term, pr)
            recall_cost += self.get_recall_cost_per(i, pr)
        for j, term in self.term_2.items():
            t2_vf_cost += self.get_t2_vf_cost_per(term, pr)
            t2_vv_cost += self.get_t2_vv_cost_per(j, pr)
            stock = self.get_t2_stock_per(j, term, pr)
            t2_hold_cost += self.get_t2_hold_cost_per(j, stock, pr)
            t2_process_cost += self.get_process_cost_per(j, pr)
            open_cost += self.get_open_cost_per(j, pr)
        rev = earning - (
                t1_vf_cost + t1_vv_cost + t1_hold_cost + recall_cost + t2_vf_cost + t2_vv_cost + t2_hold_cost + t2_process_cost + open_cost)
        self.total_revenue = rev
        return t1_vf_cost, t1_vv_cost, t1_hold_cost, t2_vf_cost, t2_vv_cost, t2_hold_cost, open_cost, recall_cost, t2_process_cost, earning

    # 以下是遗传差分算法的步骤
    def fit(self, pr: Parameters):
        self.get_term(pr)
        self.get_total_revenue(pr)

    def diff_crossover(self, cross, rate, diff1, diff2, best, factor, t2_num, pr: Parameters):
        assert isinstance(cross, Chromosome)
        assert isinstance(diff1, Chromosome)
        assert isinstance(diff2, Chromosome)
        assert isinstance(best, Chromosome)
        seq = np.zeros(len(self.sequence))
        for i in range(len(self.sequence)):
            if random.random() < rate:
                pass
                seq[i] = round(best.sequence[i] + factor * (diff2.sequence[i] - diff1.sequence[i])) % t2_num
            else:
                seq[i] = cross.sequence[i]
        c = Chromosome(-1, len(seq), 0)
        seq = seq.astype('int32')
        c.set_sequence(seq.copy())
        c.fit(pr)
        return c
